/**
 * 珠宝最高价值
 * https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
 */
class Solution1 {
    public int jewelleryValue(int[][] frame) {
        int n  = frame.length,m = frame[0].length;

        int[][] dp = new int[n+1][m+1];

        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]) + frame[i-1][j-1];
            }
        }

        return dp[n][m];
    }
}

/**
 *下降路劲最小和
 *https://leetcode.cn/problems/minimum-falling-path-sum/description/
 */
class Solution2 {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length,m = matrix[0].length;

        int[][] dp = new int[n + 1][m + 2];


        //初始化化第0，m+1列
        for(int i = 0;i <= n;i++){
            dp[i][0] = 1008611;
            dp[i][m+1] = 1008611;
        }

        //初始化首行
        for(int j = 0;j <= m + 1;j++) dp[0][j] = 0;

        //填dp表
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                int x = Math.min(dp[i-1][j-1],dp[i-1][j]);
                int y = Math.min(dp[i-1][j+1],x);
                dp[i][j] = y + matrix[i-1][j-1];
            }
        }

        //确定返回值
        int sum = 1008611;

        for(int j = 1;j <= m;j++){
            sum = Math.min(sum,dp[n][j]);
        }

        return sum;

    }
}

/**
 *最小路劲和
 * https://leetcode.cn/problems/minimum-path-sum/description/
 */
class Solution3 {
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        int[][] dp = new int[n+1][m+1];
       //首行和首列初始化
        for(int i = 0;i <= n;i++) dp[i][0] = 1008611;
        for(int j = 2;j <= m;j++) dp[0][j] = 1008611;

        for(int i = 1;i <= n;i++){
            for(int j =1;j <= m;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        return dp[n][m];
    }
}